package 每日一题;

public class No69x的平方根 {

    /**
     * 实现 int sqrt(int x) 函数。
     * 计算并返回 x 的平方根，其中 x 是非负整数。
     * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
     * <p>
     * 示例 1:
     * 输入: 4
     * 输出: 2
     * 示例 2:
     * 输入: 8
     * 输出: 2
     * 说明: 8 的平方根是 2.82842...,
     *      由于返回类型是整数，小数部分将被舍去。
     */

    //二分法
    public int mySqrt(int x) {

        if (x == 0) {
            return 0;
        }

        if (x == 1) {
            return 1;
        }

        int left = 0;
        int right = x / 2;
        int result = 0;

        while (left <= right) {
            // 除法这里需要 + 1,防止除0
            int mid = (right - left + 1) / 2 + left;

            // 用除法代理乘法,就可以不用int了
            if (mid > x / mid) {
                right = mid - 1;
            } else {
                result = mid;
                left = mid + 1;
            }

        }

        return result;
    }

    public static void main(String[] args) {
        No69x的平方根 n = new No69x的平方根();
        int result = n.mySqrt(2);
        System.out.println(result);
    }

}
